Data compression systems are useful for representing information as accurately as possible with a minimum number of bits and thus minimizing the amount of data which must be stored or transmitted in an information storage or transmission system. Wavelet transforms, otherwise known as hierarchical subband decomposition, have recently been used for low bit rate image compression because such decomposition leads to a hierarchical multi-scale representation of the source image. Wavelet transforms are applied to an important aspect of low bit rate image coding: the coding of a binary map (a wavelet tree) indicating the locations of the non-zero values, otherwise known as the "significance map" of the transform coefficients. Using scalar quantization followed by entropy coding, in order to achieve very low bit rates, e.g., less than 1 bit/pel, the probability of the most likely symbol after quantization--the zero symbol--must be extremely high. Typically, a large fraction of the bit budget must be spent on encoding the significance map. It follows that a significant improvement in encoding the significance map translates into a significant improvement in the compression of information preparatory to storage or transmission.
To accomplish this task, a new structure called a "zerotree" has been developed. A wavelet coefficient is said to be insignificant with respect to a given threshold T, if the coefficient has a magnitude less than equal to T. The zerotree is based on the hypothesis that if a wavelet coefficient at a coarse scale is insignificant with respect to a given threshold T, then all wavelet coefficients of the same orientation in the same spatial location at finer scales are likely to be insignificant with respect to T.
More specifically, in a hierarchical subband system, with the exception of the highest frequency subbands, every coefficient at a given scale can be related to a set of coefficients at the next finer scale of similar orientation according to a structure called a wavelet tree. The coefficients at the coarsest scale will be called the parent nodes, and all coefficients corresponding to the same spatial or temporal location at the next finer scale of similar orientation will be called child nodes. For a given parent node, the set of all coefficients at all finer scales of similar orientation corresponding to the same location are called descendants. Similarly, for a given child node, the set of coefficients at all coarser scales of similar orientation corresponding to the same location are called ancestors.
Nodes are scanned in the order of the scales of the decomposition, from coarsest level to finest. This means that no child node is scanned until after its parent and all other parents in all subbands at the same scale as that parent have been scanned. This is a type of modified breadth-first, subband by subband, traversal performed across all the wavelet trees defined by the coefficients of the wavelet transform of the two-dimensional data set.
Given a threshold level to determine whether or not a coefficient is significant, a node is said to be a ZEROTREE ROOT if 1) the coefficient at a node has an insignificant magnitude, 2) the node is not the descendant of a root, i.e., it is not completely predictable from a coarser scale, and 3) all of its descendants are insignificant. A ZEROTREE ROOT is encoded with a special symbol indicating that the insignificance of the coefficients at finer scales is completely predictable. To efficiently encode the binary significance map, four symbols are entropy coded: ZEROTREE ROOT, ISOLATED ZERO, and two non-zero symbols, POSITIVE SIGNIFICANT and NEGATIVE SIGNIFICANT.
U.S. Pat. No. 5,412,741 issued May 2, 1995 and herein incorporated by reference discloses an apparatus and method for encoding information with a high degree of compression. The apparatus uses zerotree coding of wavelet coefficients in a much more efficient manner than any previous techniques. The key to this apparatus is the dynamic generation of the list of coefficient indices to be scanned, whereby the dynamically generated list only contains coefficient indices for which a symbol must be encoded. This is a dramatic improvement over the prior art in which a static list of coefficient indices is used and each coefficient must be individually checked to see whether a) a symbol must be encoded, or b) it is completely predictable. The methods as discussed in the '741 patent are known as the "Embedded Zerotree Wavelet" (EZW) method.
Alternatively, the coding of wavelet trees (e.g., zerotree) can be performed depth-first across all the wavelet trees defined by the coefficients of the wavelet transform of the two-dimensional data set. This method of wavelet coding is known as Zerotree Entropy (ZTE) encoding, which is described in an U.S. patent application filed on Dec. 31, 1997 with the title "Apparatus And Method For Encoding Wavelet Trees Generated By A Wavelet-Based Coding Method" (attorney docket SAR 12234; Ser. No. 09/002,251), hereby incorporated by reference.
Although it has been found that ZTE is an effective wavelet coding method, various applications can benefit from a flexible wavelet coding method that can provide multi-scale wavelet coding, i.e., providing scalability in spatial resolution and quality.
Therefore, there is a need in the art for coding wavelet trees, which generates bitstreams with flexible degrees of spatial, quality and complexity scalabilities.